<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 打家劫舍题：
         * 输入：[1,2,3,1]
         * 输出：4
         * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
         * 偷窃到的最高金额 = 1 + 3 = 4 。 
         * 
         * 思路：
         * 
        */
        /* 
            时间：O(n) nums的长度-2
            空间：O(n) nums数组的长度
        */
        var rob = function(nums) {
           // 动态规划五部曲
           // dp[j]的含义：从0-j个房屋里面，能够打劫到的最多的金额是多少

           // 递推公式：dp[j] = Math.max(dp[j - 1], dp[j - 2] + nums[j])

           // 初始化：dp[0] = 初始化为nums[0]; dp[1]初始化为Math.max(dp[0], dp[1])

           // 遍历顺序：从前往后遍历

           // 递归例子：看语雀笔记


           // 长度为nums.length
           let dp = new Array(nums.length).fill(0)
           dp[0] = nums[0]
           // 第二个打劫的必须是第一vs第二最大的那个，
           dp[1] = Math.max(nums[0], nums[1])

           // 从2开始，0和1索引值已经初始化
           for (let j = 2; j < nums.length; j++) {
             // 递推公式解释：当前j的状态，当前j不打劫: dp[j - 1]; 打劫dp[j]：dp[j - 2] + nums[j]
             dp[j] = Math.max(dp[j - 1], dp[j - 2] + nums[j])
           }
           console.log(dp, 'dp');
           return dp[nums.length - 1]
        };
        // console.log(rob([2, 1, 1, 2]));
        console.log(rob([2, 7, 9, 3, 1]));
    </script>
</body>

</html>